package 剑指Offer._4150;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/11/15 16:02
 * 丑数
 * 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
 * 算法：动态规划
 */
public class _49 {

    public int nthUglyNumber(int n) {
        if (n <= 0) return 0;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; i++) {
            int num1 = dp[p2] * 2, num2 = dp[p3] * 3, num3 = dp[p5] * 5;
            int num = Math.min(num1, Math.min(num2, num3));
            if (num1 == num) ++p2;
            if (num2 == num) ++p3;
            if (num3 == num) ++p5;
            dp[i] = num;
        }
        return dp[n];
    }

}
